package com.ruoyi.learn.leetcode.question;

import java.util.Arrays;

/**
 * 189. 轮转数组
 * 中等
 * 相关标签
 * premium lock icon
 * 相关企业
 * 提示
 * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,2,3,4,5,6,7], k = 3
 * 输出: [5,6,7,1,2,3,4]
 * 解释:
 * 向右轮转 1 步: [7,1,2,3,4,5,6]
 * 向右轮转 2 步: [6,7,1,2,3,4,5]
 * 向右轮转 3 步: [5,6,7,1,2,3,4]
 * 示例 2:
 *
 * 输入：nums = [-1,-100,3,99], k = 2
 * 输出：[3,99,-1,-100]
 * 解释:
 * 向右轮转 1 步: [99,-1,-100,3]
 * 向右轮转 2 步: [3,99,-1,-100]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * -231 <= nums[i] <= 231 - 1
 * 0 <= k <= 105
 *
 *
 * 进阶：
 *
 * 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
 * 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
 *
 * 面试中遇到过这道题?
 * 1/5
 * 是
 * 否
 * 通过次数
 * 1,334,258/2.8M
 * 通过率
 * 47.4%
 */
public class Question189 {

    public static void main(String[] args) {
        Question189 question169 = new Question189();
        int[] nums = new int[]{1,2,3,4};
        int k = 2;
        System.out.println("nums=" + Arrays.toString(nums));
        question169.rotate(nums,k);
        System.out.println("nums=" + Arrays.toString(nums));
    }




    public void rotate(int[] nums, int k) {
        //        k = k +1;
        // 最终轮转次数
        int len = k % nums.length;
        if(len == 0){
            return;
        }
        int[] tmpArray = new int[nums.length];

        // {1,2,3,4} 变为  {3,4,1,2}

            for(int i = nums.length - 1; i >= 0; i--){

                tmpArray[i] = nums[Math.abs((i-len+nums.length)% nums.length)];
            }
            for(int i = 0; i < nums.length; i++){
                nums[i] = tmpArray[i];
            }



    }


    public void rotate1(int[] nums, int k) {


        // 最终轮转次数
        int len = k % nums.length;
        if(len == 0){
            return;
        }



        // 位置变换   i  由 (i + len)%num.length  值代替
        int count = 0;
        int lastIndex = 0;
//        int nextIndex = 0;
        // 原始值
        int lastTmp = nums[lastIndex];

        int nextTmp = nums[lastIndex];

        int nextIndex = (lastIndex + len) % nums.length;

        int last1 = 0;
        int last2 = 0;
        // 反向顺序赋值，每次只用保存被赋值的那个变量即可
        do {
//            lastTmp = nums[lastIndex];
            // i的替换索引是谁
            // sec 替换完成之后，找到下一个sec
            // 这是左轮转，需要右轮转
            nextIndex = (  len + lastIndex + nums.length) % nums.length;

            //  值会变，所以得保存一个变量
            nextTmp = nums[nextIndex];

            // 往前推看是哪个索引，赋值
            nums[nextIndex] =  lastTmp;

            if(last1 == nextIndex){

            }


            // 一次赋值结束，重置当前索引跟值
            lastIndex = nextIndex;
            lastTmp = nextTmp;


            last1 = lastIndex;
            last2 = nextIndex;



            // 重复轮转的时候需要跳出循环





            count++;

        }while (count < nums.length);


    }


}
